package org.example.algorithm.dp;

public class RobSolution {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        RobSolution robSolution = new RobSolution();
        int res = robSolution.rob(nums);
        System.out.println(res);
    }

    /**
     * dp[n] = Math.max(nums[n] + dp[n-2], dp[n-1])
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i=2;i<nums.length;i++) {
            dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
        }
        return dp[nums.length - 1];
    }

    /**
     * F(0, n-1) = Math.max(nums[0] + F(2,n-1), F(1,n-1))
     * F(start, end) = Math.max(nums[start] + F(start+2,end), F(start+1,end))
     * @param nums
     * @return
     */
    public int rob2(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i=2;i<nums.length;i++) {
            dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
        }
        return dp[nums.length - 1];
    }
}
